1. Field of the Invention
This invention relates to address transformation systems and more particularly to such systems having an address translator with a translation address distribution limitation and an address shuffler coupled to generate shuffled addresses which avoid the distribution limitation.
2. Discussion of the Prior Art
Data storage devices have become increasingly larger in recent years in order to meet the demands of the data processing industry for ever more storage and in order to reduce manufacturing costs. However, as data store sizes increase it becomes increasingly difficult to produce defect free components. A single defect within a batch fabricated component such as a semiconductor memory chip may require the discarding of the entire component or at least a significant portion of the component. Other data storage components such as some types of core memories may be repairable, but at relatively high cost.
In order to avoid disposal of an expensive component because of a relatively small number of defects, address transformation systems have been developed which translate an input address for a defective data store location to a different, valid data store location. Upon manufacture of a data store component, the component is tested to identify defective storage locations. The address transformation system is then programmed to recognize the defective address locations and translate any such address to a different, valid address location. Except for possible time delay penalties under some arrangements, an external device using the data store is unaware that any address translation has taken place.
One example of such an address transformation system is disclosed in application Ser. No. 279,204, filed June 30, 1981 for "Selective Mapping System and Method" by Thomas J. Gilligan. Other systems are disclosed in U.S. Pat. Nos. 3,633,175 Harper and 4,310,901 to Harding et al.
Typically these address transformation systems partition incoming address signals into two or more ordered sets. One set can be said to select one of many pages and the other set can be said to identify a particular address on the selected page. If the number of defective locations associated with any single page exceeds a certain given number, the system fails. Usually an economic tradeoff must be made between the cost of the transformation system and the limitations on the number and distribution of defective addresses that can be accommodated.
For example, in the above-mentioned system of Thomas J. Gilligan, an address transformation system for a 512K word core memory can accommodate up to 4K defective address locations if they are properly distributed. However, there may be no more than 64 faults associated with any single page, whether an A page or a B page, and accommodating all defects becomes increasingly difficult as the maximum number of 4K defects is approached. It is estimated that with the maximum number of 4K randomly distributed defects, the probability of more than 64 defects occurring on any single addressing page is less than one in 100,000.
However, any memory system will tend to experience the occurrence on nonrandom defects. For example, a defective current line or in a core memory a noisy or defective sense winding may result in unsatisfactory operation at a large number of physically related data storage locations. Because economy of manufacture often requires address decoders to associate address pages with certain sense windings or control lines, a single defect may cause a large number of memory defects to occur on the same addressing page. This can cause an address translation system to fail even though the total number of data store faulty address locations is less than the maximum for the address translation system. The present invention shuffles the input addresses relative to the actual data store addresses in such a way that grouped data store defects will be distributed over multiple addressing pages so that an address translation system need not fail because of the nonrandom occurrence of multiple defects.